<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>2.3.- spinsort</title>
<link rel="stylesheet" href="../../../../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../../index.html" title="Boost.Sort">
<link rel="up" href="../single_thread.html" title="2.- Single Thread Algorithms">
<link rel="prev" href="pdqsort/pdqsort_bad_partitions.html" title="Bad Partitions">
<link rel="next" href="spinsort/spinsort_benchmark.html" title="Benchmark">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
<td align="center"><a href="../../../../../../index.html">Home</a></td>
<td align="center"><a href="../../../../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort/pdqsort_bad_partitions.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="spinsort/spinsort_benchmark.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h3 class="title">
<a name="sort.single_thread.spinsort"></a><a class="link" href="spinsort.html" title="2.3.- spinsort">2.3.- spinsort</a>
</h3></div></div></div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.single_thread.spinsort.spinsort_description"></a><a class="link" href="spinsort.html#sort.single_thread.spinsort.spinsort_description" title="Description">Description</a>
</h4></div></div></div>
<div class="blockquote"><blockquote class="blockquote">
<p>
            <span class="bold"><strong>Spinsort</strong></span> is a new stable sort algorithm,
            designed and implemented by Francisco Tapia for the Boost Sort Library.
          </p>
<p>
            This algorithm combines several ideas used to optimize other stable sort
            algorithms.
          </p>
<p>
            <span class="bold"><strong>
<pre class="programlisting">            |         |                   |                                |
Algorithm   | Stable  | Additional Memory | Best, average, and worst case  |
------------+---------+-------------------+--------------------------------+
spinsort    |   Yes   |      N / 2        |     N, NlogN , NlogN           |
            |         |                   |                                |
</pre>
            </strong></span>
          </p>
<p>
            The algorithm is most efficient when the data are nearly sorted. Many
            times the new elements are inserted at the end of the sorted elements,
            or some elements are modified, breaking the order of the elements. In
            these cases, spinsort is very fast.
          </p>
</blockquote></div>
</div>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven
      Ross, Francisco Tapia, Orson Peters<p>
        Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
        Software License, Version 1.0</a>.
      </p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="pdqsort/pdqsort_bad_partitions.html"><img src="../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../single_thread.html"><img src="../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="spinsort/spinsort_benchmark.html"><img src="../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
